package com.xupt.easy.string;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author zhaoxin
 * @title: IsValid
 * @projectName LeetCode
 * @description: 有效的括号
 * @date 2019/12/4 10:01
 */
public class IsValid020 {

    private Map<String, String> map = new HashMap<>();

    public IsValid020() {
        this.map.put(")", "(");
        this.map.put("]", "[");
        this.map.put("}", "{");
    }

    /**
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
     *
     * 有效字符串需满足：
     *
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     * 注意空字符串可被认为是有效字符串。
     *
     * 示例 1:
     *
     * 输入: "()"
     * 输出: true
     * 示例 2:
     *
     * 输入: "()[]{}"
     * 输出: true
     * 示例 3:
     *
     * 输入: "(]"
     * 输出: false
     * 示例 4:
     *
     * 输入: "([)]"
     * 输出: false
     * 示例 5:
     *
     * 输入: "{[]}"
     * 输出: true
     *
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        Stack<String> strStack = new Stack<>();

        String [] strArray = s.split("");

        for (String str : strArray) {
            if ("".equals(str)){
                return true;
            }

            if (this.map.containsKey(str)){
                strStack.push(str);
            }else {
                String popStr = strStack.isEmpty() ? "$" : strStack.pop();
                if (!popStr.equals(this.map.get(str))){
                    return false;
                }
            }

        }

        return strStack.isEmpty();
    }

    public static void main(String[] args) {

        IsValid020 isValid020 = new IsValid020();

        isValid020.isValid("])");

    }


}
